public class Rainy {
    // https://leetcode.cn/problems/trapping-rain-water/
    class Solution {
        public int trap(int[] height) {
            int [] left = new int[height.length + 2];
            for(int i = 0 ; i < height.length ; i ++)
            {
                if(height[i] > left[i])
                {
                    left[i+1] = height[i];
                }else
                {
                    left[i+1] = left[i];
                }
            }
            int [] right = new int[height.length + 2];
            for(int i = height.length - 1; i >= 0 ; i --)
            {
                if(height[i] > right[i+1])
                {
                    right[i] = height[i];
                }else
                {
                    right[i] = right[i+1];
                }
            }
            int res = 0;
            for(int i = 0 ; i < height.length ; i ++)
            {
                int l = left[i+1];
                int r = right[i];
                int t = Math.min(l,r) - height[i];
                if(t > 0) res += t;
            }

            return res;


        }
    }
}
